package leetcode.editor.day;

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 828. 统计子串中的唯一字符
// https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/
class CountUniqueCharactersOfAllSubstringsOfAGivenString {
    public static void main(String[] args) {
        Solution solution = new CountUniqueCharactersOfAllSubstringsOfAGivenString().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/solution/tong-ji-zi-chuan-zhong-de-wei-yi-zi-fu-b-h9pj/
        // 记录前面字符串前面两个出现的位置
        // 例如 ABACA，求字符A出现次数，此时A出现在0，2，4位置，所有的唯一字符为(2 - 0) * (4 - 2) = 4个
        // 也就是中间的A只出现一次 A , BA , BAC , AC

        // 时间复杂度：O(n)，其中 n 是 s 的长度。每个下标会被计算一次。
        // 空间复杂度：O(n)，哈希表占用 O(n) 空间。
        public int uniqueLetterString(String s) {
            int n = s.length();
            Map<Character, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                if (!map.containsKey(c)) {
                    // 不存在的话放入-1，便于计算
                    map.put(c, new ArrayList<>());
                    map.get(c).add(-1);
                }
                // 放入当前索引
                map.get(c).add(i);
            }

            int ans = 0;
            for (Map.Entry<Character, List<Integer>> entry : map.entrySet()) {
                List<Integer> arr = entry.getValue();
                // 加入长度方便计算
                arr.add(n);
                for (int i = 1; i < arr.size() - 1; i++) {
                    ans += (arr.get(i) - arr.get(i - 1)) * (arr.get(i + 1) - arr.get(i));
                }
            }

            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
